# LeetCode 739、每日温度

# 一、题目描述

根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

# 二、题目解析

这道题目最 “难” 的一个点是题目的理解。

给定列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],为啥输出就是 [1, 1, 4, 2, 1, 1, 0, 0]

下面来一个个进行解释。

对于输入 73,它需要 经过一天 才能等到温度的升高,也就是在第二天的时候,温度升高到 74 ,所以对应的结果是 1。

对于输入 74,它需要 经过一天 才能等到温度的升高,也就是在第三天的时候,温度升高到 75 ,所以对应的结果是 1。

对于输入 75,它经过 1 天后发现温度是 71,没有超过它,继续等,一直 等了四天,在第七天才等到温度的升高,温度升高到 76 ,所以对应的结果是 4 。

对于输入 71,它经过 1 天后发现温度是 69,没有超过它,继续等,一直 等了两天,在第六天才等到温度的升高,温度升高到 72 ,所以对应的结果是 2 。

对于输入 69,它 经过一天 后发现温度是 72,已经超过它,所以对应的结果是 1 。

对于输入 72,它 经过一天 后发现温度是 76,已经超过它,所以对应的结果是 1 。

对于输入 76,后续 没有温度 可以超过它,所以对应的结果是 0 。

对于输入 73,后续 没有温度 可以超过它,所以对应的结果是 0 。

也就是说,这道题目就是给你一个值,让你找到右边第一个比它大的数,它们两则的下标差就是输出结果

好了,理解了题意我们来思考如何求解:借助单独递增栈来处理。

具体操作如下:

遍历整个数组,如果栈不空,且当前数字大于栈顶元素,那么如果直接入栈的话就不是 递增栈 ,所以需要取出栈顶元素,由于当前数字大于栈顶元素的数字,而且一定是第一个大于栈顶元素的数,直接求出下标差就是二者的距离。

继续看新的栈顶元素,直到当前数字小于等于栈顶元素停止,再将数字入栈,这样就可以一直保持递增栈,且每个数字和第一个大于它的数的距离也可以算出来。

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 每日温度( LeetCode 739 ):https://leetcode-cn.com/problems/daily-temperatures
class Solution {
    /**
     * 维护一个单调递增栈,栈内元素从栈底到栈顶依次减小
     * 入栈的元素要和当前栈内栈首元素进行比较
     * 如果大于栈首元素,说明温度比之前更高,那么它们的下标差就是栈首元素等了多少天等到的更高温度的结果
     * 如果小于栈首元素,说明温度比之前更低,说明还没有等到更高的温度,直接放入到栈中
     */
    public static int[] dailyTemperatures(int[] temperatures) {

        // 构建一个栈,用来存放每日温度的下标
        Stack<Integer> stack = new Stack<>();

        // 构建一个数组,用来保存输出结果
        int[] res = new int[temperatures.length];

        // 从头开始遍历每天的温度
        for (int i = 0; i < temperatures.length; i++) {

            // 拿到当天的温度,需要和栈首元素进行比较
            // 如果此时栈不为空并且当天的温度大于栈首元素
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                
                // 首先获取栈首元素的值,并将元素从栈中移除
                int preIndex = stack.pop();

                // 它们的下标差就是栈首元素等了多少天等到的更高温度的结果,保存到输出数组 res 中
                res[preIndex] = i - preIndex;
            }
           
            // 再把当天的温度的下标值存放到栈中
            stack.push(i);
        }
        // 最后输出 res 数组即可
        return res;
    }

}

# **2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 每日温度( LeetCode 739 ):https://leetcode-cn.com/problems/daily-temperatures
/**
* 维护一个单调递增栈,栈内元素从栈底到栈顶依次减小
* 入栈的元素要和当前栈内栈首元素进行比较
* 如果大于栈首元素,说明温度比之前更高,那么它们的下标差就是栈首元素等了多少天等到的更高温度的结果
* 如果小于栈首元素,说明温度比之前更低,说明还没有等到更高的温度,直接放入到栈中
*/
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
  // 构建一个栈,用来存放每日温度的下标
        stack<int> stk;

        // 构建一个数组,用来保存输出结果
        vector<int> res(T.size());

        // 从头开始遍历每天的温度
        for (int i = 0; i < T.size(); i++) {

            // 拿到当天的温度,需要和栈首元素进行比较
            // 如果此时栈不为空并且当天的温度大于栈首元素
            while (!stk.empty() && T[i] > T[stk.top()]) {
                
                // 首先获取栈首元素的值,并将元素从栈中移除
                int preIndex = stk.top();

                stk.pop();

                // 它们的下标差就是栈首元素等了多少天等到的更高温度的结果,保存到输出数组 res 中
                res[preIndex] = i - preIndex;
            }
           
            // 再把当天的温度的下标值存放到栈中
            stk.push(i);
        }
        // 最后输出 res 数组即可
        return res;
    }
};

# 3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 每日温度( LeetCode 739 ):https://leetcode-cn.com/problems/daily-temperatures
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        # 构建一个栈,用来存放每日温度的下标
        stack = []

        # 获取数组长度
        length = len(temperatures)
        
        # 构建一个数组,用来保存输出结果
        res = [0] * length

        # 从头开始遍历每天的温度
        for i in range(length):
            #  拿到当天的温度,不断的和栈顶元素进行比较
            temperature = temperatures[i]

            # 如果栈顶元素存在并且当天的温度大于栈顶元素
            # 意味着栈顶元素等到了第一个温度比它更高的那一天
            # 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果
            while stack and temperature > temperatures[stack[-1]]:

                # 首先获取栈顶元素的值,也就是每日温度的下标值
                preIndex = stack.pop()

                # 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果,保存到输出数组 res 中
                res[preIndex] = i - preIndex


            # 再把当天的温度的下标值存放到栈中
            # 注意:是下标索引值
            stack.append(i)

        # 最后输出 res 数组即可
        return res

# 四、复杂度分析

时间复杂度:O(n),其中 n 是温度列表的长度。正向遍历温度列表一遍,对于温度列表中的每个下标,最多有一次进栈和出栈的操作。

空间复杂度:O(n),其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。